/*
 * CsbIndex.cpp
 *
 *  Created on: Oct 10, 2011
 *      Author: USHonDan
 */

#include <math.h>
#include <string.h>
#include "CsbIndex.h"

using namespace std;

//initialize CsbIndex to predefined constant used by Node class and specified in Node::GetD()
CsbIndex::CsbIndex(int d) : _d(d) {
	//initialize with single root index node and empty leaf node as part of preallocated lead node nodegroup
	_root = new IndexNode();
	_root->_child = allocateNodeGroup(LEAF_NODE);
	LeafNode *firstLeaf = new (_root->_child) LeafNode(); //placement new
	firstLeaf->SetPrevious(NULL);
	firstLeaf->SetNext(NULL);

	resetStack();
	resetQueue();
}

CsbIndex::~CsbIndex() {
	//clean out stack
	stackElement *removedEle = NULL;
	while(!_stack.empty()) {
		removedEle = _stack.top();
		delete removedEle;
		_stack.pop();
	}

	//TODO: delete tree of created nodes to avoid memory leak
	delete _root;
}

//Output all keys in leaf nodes
void CsbIndex::printKeys() {
	Node *node = _root;

	while(node->GetNodeType() != LEAF_NODE) {
		node = ((IndexNode *)node)->GetChildNode(0);
	}

	while(node != NULL) {
		printKeysNode(node);
		node = ((LeafNode *)node)->GetNext();
	}
}

//Search for record with specified key
//Returns NULL if key not found
Record *CsbIndex::searchRecord(int searchKey) {
	Node *currentNode = _root;
	while(currentNode->GetNodeType() != LEAF_NODE) {
		currentNode = ((IndexNode *)currentNode)->SearchKeyNextChild(searchKey);
	}

	return  ((LeafNode *)currentNode)->GetRecord(searchKey);
}

//Print full index
void CsbIndex::printIndex() {
	int length=0;
	Node* front= _queue.front();

	if(front->GetNodeType() == INDEX_NODE) {
		length = _queue.size();
		printLevel();
		for(int x=0; x < length; x++) {
			Node *temp = _queue.front();
			_queue.pop();
			addNodesToQueue((IndexNode *)temp);
		}
		printIndex();
	}
	else {
		printLevel();
		resetQueue();
	}

}

//Prints all keys on a level
void CsbIndex::printLevel() {
	for(int x=0; x < _queue.size(); x++) {
		Node *temp = _queue.front();
		printKeysNode(temp);
		_queue.pop(); //pop-push to rotate around in queue (put in back of line again)
		_queue.push(temp);
	}
	cout << endl;
}

//Prints all keys in a node
void CsbIndex::printKeysNode(Node *node) {
	for(int x=0; x < node->NumberOfKeys(); x++) {
		if(x != node->NumberOfKeys()-1)
			cout << node->_keys[x] << ", ";
		else
			cout << node->_keys[x]  << "\t\t";
	}
}

//Helper function to add all leaf nodes to the queue for printing
void CsbIndex::addNodesToQueue(IndexNode* node) {
	for(int x=0; x <= node->NumberOfKeys(); x++)
		_queue.push(node->GetChildNode(x));
}

//Splits leaf node into next leaf node space in nodegroup, pushing additional nodes further down
//Return last key in first node
int CsbIndex::splitLeafNode(LeafNode *leafToSplit, int nodeGroupIndex, IndexNode *indexAbove) {
	int divIndex = (int)ceil((_d+1)/2.0) - 1;

	LeafNode *leafPtr;
	LeafNode *prev = NULL;
	//Advance leaf nodes in node group
	LeafNode *startCpy = (LeafNode *)indexAbove->GetChildNode(nodeGroupIndex+1);
	memmove(startCpy+1, startCpy, sizeof(LeafNode) * (indexAbove->NumberOfKeys() - nodeGroupIndex));
	for(int idx = indexAbove->NumberOfKeys(); idx > nodeGroupIndex; idx--) {
		leafPtr = (LeafNode *)indexAbove->GetChildNode(idx);
		if(prev != NULL)
			leafPtr->SetNext(prev); //only adjust next pointer if already initialized
		(leafPtr+1)->SetPrevious(leafPtr);
		prev = leafPtr+1;
	}
//	for(int idx = indexAbove->NumberOfKeys(); idx > nodeGroupIndex; idx--) {
//		leafPtr = (LeafNode *)indexAbove->GetChildNode(idx);
//		memcpy(leafPtr+1, leafPtr, sizeof(LeafNode));
//		if(prev != NULL)
//			leafPtr->SetNext(prev); //only adjust next pointer if already initialized
//		(leafPtr+1)->SetPrevious(leafPtr);
//		prev = leafPtr+1;
//	}
	leafPtr = new (leafToSplit + 1) LeafNode();
	leafPtr->SetNext(prev);

	int lastIdx = leafToSplit->SplitLeaf(leafPtr, divIndex+1);

//	indexAbove->InsertKey(lastIdx);

	return lastIdx;
}

//Split index node into next index node slot in nodegroup, and create new nodegroup under new node (redistributing original nodegroup's nodes as well)
//Return last key in first node
int CsbIndex::splitIndexNode(IndexNode *indexToSplit, int nodeGroupIndex, IndexNode *indexAbove) {
	int divIndex = (int)ceil((_d+1)/2.0) - 1;

	IndexNode *indexPtr = (IndexNode *)indexAbove->GetChildNode(nodeGroupIndex+1);
	memmove(indexPtr + 1, indexPtr, sizeof(IndexNode) * (indexAbove->NumberOfKeys() - nodeGroupIndex));
//	for(int idx = indexAbove->NumberOfKeys(); idx > nodeGroupIndex; idx--) {
//		indexPtr = (IndexNode *)indexAbove->GetChildNode(idx);
//		memcpy(indexPtr+1, indexPtr, sizeof(IndexNode));
//	}
	indexPtr = new (indexToSplit + 1) IndexNode();

	//Split children nodegroup into two nodegroups -- would be in IndexNode::SplitIndexNode except that allocateNodeGroup function is part of index scope
	NodeType childType = indexToSplit->GetChildNode(0)->GetNodeType();
	Node *newNodeGroup = allocateNodeGroup(childType);
	int numNodesInNewNodeGroup = indexToSplit->NumberOfKeys() - divIndex;
	if(childType == INDEX_NODE) {
		memcpy(newNodeGroup, ((IndexNode *)indexToSplit->GetChildNode(0)) + divIndex + 1,
				sizeof(IndexNode)*(numNodesInNewNodeGroup));
	}
	else {
		memcpy(newNodeGroup, ((LeafNode *)indexToSplit->GetChildNode(0)) + divIndex + 1,
				sizeof(LeafNode)*(numNodesInNewNodeGroup));
		LeafNode *ptr = (LeafNode*)newNodeGroup;
		((LeafNode *)indexToSplit->GetChildNode(divIndex))->SetNext(ptr);
		for(int idx = 0; idx < numNodesInNewNodeGroup; idx++) {
			if(idx != numNodesInNewNodeGroup - 1)
				ptr->SetNext(ptr + idx + 1);
			if(idx > 0)
				ptr->SetPrevious(ptr + idx - 1);
		}
	}

	indexPtr->_child = newNodeGroup;
	int lastIdx = indexToSplit->SplitIndexNode(indexPtr, divIndex+1);

//	indexAbove->InsertKey(lastIdx);

	return lastIdx;
}

//Allocates space for a nodegroup of the input type
Node *CsbIndex::allocateNodeGroup(NodeType type) {
	Node *firstLeaf = NULL;

	if(type == LEAF_NODE)
		firstLeaf = (Node*) new char[sizeof(LeafNode) * (_d + 2)]; //allocate space for nodegroup, don't initialize
	else
		firstLeaf = (Node*) new char[sizeof(IndexNode) * (_d + 2)];

	return firstLeaf;
}

//Insert record into CSB+Tree index
Record *CsbIndex::insertRecord(int insertKey, Record *record) {
	return insertRecord(_root, insertKey, record);
}

Record *CsbIndex::insertRecord(IndexNode *currentNode, int insertKey, Record *record) {
	//short circuit: don't insert NULL records
	if(record == NULL)
		return NULL;

	//ASSERT: will always be index node
	int x = currentNode->SearchKey(insertKey);

	//short circuit: can't insert if record already exists
	if(currentNode->_keys[x] == insertKey)
		return NULL;

	//nextNode points to the nextNode where the record belongs
	Node* nextNode = currentNode->GetChildNode(x);

	if(nextNode->GetNodeType() == LEAF_NODE) {
		LeafNode *nextLeaf = (LeafNode *)nextNode;
		if(nextLeaf->NeedsSplit()) { //checks to see space is available for a record insertion
			if(nextLeaf->InsertRecord(insertKey, record) == -1) //insert record so d+1 records pointed to by leaf node
				return NULL; //logic error -- attempted to insert index into "super" full node or where key already exists

			//Split leaf node and move others in node group to right
			//Fix next/prev pointers on split and insertion
			int newKey = splitLeafNode(nextLeaf, x, currentNode);

			while(currentNode->NeedsSplit()) { //if need to split, insert key and perform split, bubbling up to root
					currentNode->InsertKey(newKey);

					//special handling if bubble up to root
					if(currentNode == _root) {
						_root = new IndexNode();
						IndexNode *newNodeGroup = (IndexNode *)allocateNodeGroup(INDEX_NODE);
						memcpy(newNodeGroup, currentNode, sizeof(IndexNode));
						delete currentNode; //cleanup old root node
						_root->_child = newNodeGroup;
						newKey = splitIndexNode(newNodeGroup, 0, _root);
						currentNode = _root; //set current node to root so final key insert is correct

						resetQueue(); //new root, need to reset queue for index printing
					}
					else {
						stackElement *prevEle = _stack.top();
						IndexNode *nodeAbove = (IndexNode *)prevEle->node;
						newKey = splitIndexNode(currentNode, prevEle->index, nodeAbove);
						currentNode = nodeAbove;
						_stack.pop();
						delete prevEle; //cleanup
					}
			}
			currentNode->InsertKey(newKey); //end bubbled key adds with final key insertion

			resetStack();
			return record;
		}
		else {
			int cleanInsertIdx = ((LeafNode *)nextNode)->InsertRecord(insertKey, record);

			resetStack();

			if(cleanInsertIdx != -1)
				return record;
			else
				return NULL;
		}
	}
	else {
		stackElement *currentStack = new stackElement();
		currentStack->node = currentNode;
		currentStack->index = x;
		_stack.push(currentStack); //modify top of stack to show which branch was taken

		return insertRecord((IndexNode *)nextNode, insertKey, record); //recursively call insertRecord to look through child node
	}
}

//Used to keep track of the current Node level while inserting
void CsbIndex::resetStack() {
	stackElement *stackEle = new stackElement();
	stackEle->node = _root;
	stackEle->index = 0;
	stackElement *removedEle = NULL;
	while(!_stack.empty()) {
		removedEle = _stack.top();
		delete removedEle;
		_stack.pop();
	}
//	_stack.push(stackEle); //leave stack empty
//	while(_stack.size() > 1)
//		_stack.pop();
}

//Used to keep track of the current Node level while printing index
void CsbIndex::resetQueue() {
	while(!_queue.empty())
		_queue.pop();

	_queue.push(_root);
}
